'''
https://leetcode.cn/problems/minimum-insertion-steps-to-make-a-string-palindrome/description/
'''


class Solution:
    def minInsertions(self, s: str) -> int:
        def f(i, j):
            if i >= j:
                return 0
            if s[i] == s[j]:
                return f(i + 1, j - 1)
            return 1 + min(f(i + 1, j), f(i, j - 1))
        return f(0, len(s) - 1)

    # 改打表
    def minInsertions2(self, s: str) -> int:
        n = len(s)
        dp = [[0] * n for _ in range(n)]
        # 第一维度依赖后边，第二维度依赖前边
        # 依赖左下角，下边，左边
        # 普遍位置 从下往上，从左往右
        # 第n-1行，第0列怎么填?
        #       第0列全是0因为        i >= j: return 0
        #       第n-1行也都是0因为    i >= j: return 0
        for i in range(n-2, -1, -1):
            for j in range(i+1, n):     # j <= i: return 0
                if s[i] == s[j]:
                    dp[i][j] = dp[i + 1][j - 1]
                else:
                    dp[i][j] = 1 + min(dp[i + 1][j], dp[i][j - 1])
        return dp[0][n - 1]
